package com.aqie.easy.sort;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

/**
 * 506 相对名次
 */
public class FindRelativeRanks {
    /**
     * map 倒序遍历
     * @param nums
     * @return
     */
    public String[] findRelativeRanks2(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();

        for (int i = 0;i < nums.length;i++) {
            map.put(nums[i],i);
        }

        Arrays.sort(nums);
        int order = 1;
        String ans[] = new String[nums.length];

        for (int i = nums.length - 1;i >= 0;i--) {
            int key = nums[i];
            switch(order) {
                case 1:
                    ans[map.get(key)] = "Gold Medal";
                    break;
                case 2:
                    ans[map.get(key)] = "Silver Medal";
                    break;
                case 3:
                    ans[map.get(key)] = "Bronze Medal";
                    break;
                default:
                    ans[map.get(key)] = String.valueOf(order);
            }

            order++;
        }

        return ans;
    }


    /**
     * 快排
     * @param nums
     * @return
     */
    public String[] findRelativeRanks(int[] nums) {
        int[] ranks = new int[nums.length];
        for(int i = 0, iMax = nums.length;i < iMax;i++) {
            ranks[i] = i;
        }
        quickSort(nums, ranks, 0, nums.length - 1);
        String[] result = new String[nums.length];
        for(int i = 0, iMax = nums.length;i < iMax;i++) {
            switch(i) {
                case 0:
                    result[ranks[i]] = "Gold Medal";
                    break;
                case 1:
                    result[ranks[i]] = "Silver Medal";
                    break;
                case 2:
                    result[ranks[i]] = "Bronze Medal";
                    break;
                default:
                    result[ranks[i]] = Integer.toString(i + 1);
                    break;
            }
        }
        return result;
    }

    private void quickSort(int[] nums, int[] ranks, int first, int last) {
        if(first >= last) {
            return;
        }
        int pos = getPosition(nums, ranks, first, last);
        quickSort(nums, ranks, first, pos - 1);
        quickSort(nums, ranks, pos + 1, last);
    }

    private int getPosition(int[] nums, int[] ranks, int first, int last) {
        int pos = first - 1, target = nums[last], temp = 0;
        for(;first < last;first++) {
            if(nums[first] > target) {
                pos++;
                temp = nums[pos];
                nums[pos] = nums[first];
                nums[first] = temp;
                temp = ranks[pos];
                ranks[pos] = ranks[first];
                ranks[first] = temp;
            }
        }
        pos++;
        temp = nums[pos];
        nums[pos] = nums[last];
        nums[last] = temp;
        temp = ranks[pos];
        ranks[pos] = ranks[last];
        ranks[last] = temp;
        return pos;
    }

    public static void main(String[] args) {
        // int[] 转 Integer[]
        int[] nums = {1,3,2};
        Integer[] copy = new Integer[nums.length];
        for (int i = 0; i < nums.length;i++){
            copy[i] = nums[i];
        }
        // 默认升序
        Comparator cmp = new FindRelativeRanks().new MyComparator();
        Arrays.sort(copy, cmp);
        System.out.println(Arrays.toString(copy));
    }
    class MyComparator implements Comparator<Integer>{
        // o1 < o2 返回正值
        @Override
        public int compare(Integer o1, Integer o2) {
            return o2 - o1;
        }
    }


}
